package weekMatch.two_102;

import java.util.*;

class Graph {

    int[][] dp;

    public Graph(int n, int[][] edges) {
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], 10000_0000);
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }
        for (int[] edge : edges) {
            dp[edge[0]][edge[1]] = edge[2];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] > dp[i][k] + dp[k][j]){
                        dp[i][j] = dp[i][k] + dp[k][j];
                    }
                }
            }
        }
    }
    
    public void addEdge(int[] edge) {
        if (dp[edge[0]][edge[1]] > edge[2]){
            dp[edge[0]][edge[1]] = edge[2];
            int n = dp.length;
            for (int k = 0; k < n; k++) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (dp[i][j] > dp[i][k] + dp[k][j]){
                            dp[i][j] = dp[i][k] + dp[k][j];
                        }
                    }
                }
            }
        }
    }

    public int shortestPath(int node1, int node2) {
        return dp[node1][node2] == 10000_0000 ? -1 : dp[node1][node2];
    }
}